Trusted e-mail communication in a multi-tenant environment is a process for authenticating messages received from multi-tenant systems. In some situations, an organization may receive e-mails from multiple other organizations. The organization may wish to apply certain message handling rules to messages authenticated as being from specific other organizations, but subject other messages to different rules. Conventional e-mail systems may employs certificate-based authentication and/or IP-address-based authentication to establish a trusted communication channel with another organization's e-mail system. These techniques, however, may only be useful when both sides of the trusted channel host their own e-mail systems on their premises. When either party (or both parties) uses an e-mail service hosted by a service provider, the provider's certificate and IP addresses may be shared between all customers of that service provider and may not be sufficient to establish a trusted communication channel with a specific customer of the service provider (aka tenant).